suppressPackageStartupMessages({
  library(tidyverse)
  library(glue)
  library(GGally)
  library(ggridges)
  library(plotly)
  library(factoextra)
  library(amap)
  library(sf)
  library(igraph)
  # remotes::install_github("rpkgs/gg.layers")
  library(gg.layers)
})

Datos

Leemos los datos del Banco Mundial con indicadores por países que se encuentran en data/worldbank.csv. En data/world_bankmetadata.csv podemos revisar los metadatos de cada indicador. data/worldbank_sf.rds contiene los datos necesarios para hacer mapas.

dat = read_csv("data/worldbank.csv")
dat_sf = readRDS("data/worldbank_sf.rds")

Análisis exploratorio I

Echamos un vistazo a los datos.

dim(dat)
[1] 176  13
names(dat)
 [1] "iso3c"        "country"      "date"         "densidad"    
 [5] "pib_capita"   "uhc"          "exp_vida"     "porc_14"     
 [9] "porc_65"      "pob"          "porc_urban"   "region"      
[13] "income_level"
head(dat)
NA

Descartamos variables irrelevantes.

dat = dat %>% select(-c(date)) # descartamos el año

Vemos los países con los valores más bajos y más altos por variable

# variables de "ID" (y que no sirven para agrupar)
id_cols = c("iso3c", "country", "region", "income_level")
dat_tmp = dat %>% 
  # formato long
  pivot_longer(-all_of(id_cols), names_to="variable", values_to="value") %>% 
  arrange(variable) %>% 
  select(-iso3c, -region, -income_level) %>% 
  # valores ordenados por variable
  group_by(variable) %>% 
  arrange(-value) 
# data.frame con top3 y bottom3 por variable
rdo = bind_rows(
  dat_tmp %>% top_n(3, value) %>% ungroup()
  ,dat_tmp %>% top_n(-3, value) %>% ungroup()
) %>% 
  arrange(variable, value)

# print: un dataframe por cada variable
print( split(rdo, rdo$variable) )
$densidad

$exp_vida

$pib_capita

$pob

$porc_14

$porc_65

$porc_urban

$uhc
### alternativa:
# for (var_ in names(dat)) {
#   tmp = dat %>% 
#     arrange(!!sym(var_)) %>% 
#     select(country, var_)
#   top = tmp %>% head(3)
#   bottom = tmp %>% tail(3)
#   print(var_)
#   print(bind_rows(top, bottom))
# }
###

Graficamos la distribución de cada variable por separado:

# formato long
gdat = dat %>%
  pivot_longer(-all_of(id_cols), names_to="variable", values_to="value")
# plot de densidad por variable
plt = 
  ggplot(gdat) +
  geom_density(aes(x=value), fill="red", alpha=0.2) +
  facet_wrap(~variable, scales = "free") +
  theme_minimal() +
  NULL

print(plt)

Analizamos las correlaciones entre las variables:

# dataframe con variables numericas
dat_num = dat %>% select_if(is.numeric)
# matriz de correlaciones como plot
plt = GGally::ggcorr(dat_num, label=T, method=c("all.obs","spearman"))

print( plt )


### opcion interesante para graficar:
# GGally::ggpairs()

Preprocesamiento

Creamos un data.frame con las variables que usaremos para agrupar países.

Vamos a normalizar estas variables para que estén en escalas comparables. Este paso se conoce como scaling. Las normalizaciones más comunes son:

  • estandarización media-desvío

\[ \frac{x - avg(x)}{sd(x)} \]

Todas las variables quedan con media 0 y desvío 1, y las unidades representan desvíos con respecto a la media. Las variables con más valores extremos tendrán un rango más alto que el resto.

  • min-max

\[ \frac{x - min(x)}{max(x) - min(x)} \] Todas las variables quedan expresadas en el rango 0-1. Las medias y los desvíos de las variables no son iguales, a diferencia de la estandarización convencional.

  • estandarización robusta

\[ \frac{x - median(x)}{IQR(x)} \]

En lugar de usar la media y la varianza, se usa la mediana y el rango intercuartílico. Este tipo de normalización es robusta a valores extremos por variable.

# funciones (udf) para normalizar
minmax = function(x) (x - min(x)) / (max(x) - min(x))
rob_scale = function(x) (x - median(x)) / IQR(x)
# data numerica normalizada
dat_c = dat %>%
  select_if(is.numeric) %>% 
  # scale(center=T, scale=T) %>% # estandarizacion media-desvio
  mutate_all(rob_scale) %>% # normalizacion
  as.data.frame() # las funciones de cluster se llevan mejor con data.frame (admite row.names)

Análisis exploratorio II

Analizamos los perfiles de los países en términos de las variables. Este gráfico nos puede servir para definir la noción de similitud/disimilitud apropiada para nuestro problema.

# formato long con datos normalizados
gdat = dat %>%
  mutate_if(is.numeric, rob_scale) %>% 
  pivot_longer(
    -all_of(id_cols), names_to="variable", values_to="value"
  )
# plot de coordenadas paralelas
plt = ggplot(gdat, aes(x=variable, y=value, group=country)) +
  geom_line(alpha=0.3) +
  geom_line(data=filter(gdat, country=="Argentina")
            , color="red", alpha=0.3) +
  theme_minimal()

# plot interactivo
ggplotly(plt, width=860, height=500)
NA
# lo mismo pero sin outliers...
gdat_sin_outliers = gdat %>% 
  filter(!country %in% c("India","China","Singapore"))
plt_sin_outliers = 
  ggplot(gdat_sin_outliers, aes(x=variable, y=value, group=country)) +
  geom_line(alpha=0.3) +
  geom_line(data=filter(gdat, country=="Argentina")
            , color="red", alpha=0.3) +
  theme_minimal()

ggplotly(plt_sin_outliers, width=860, height=500)

### alternativa:
# GGally::ggparcoord()
###

Por ejemplo, si usamos la disimilitud de correlación como métrica, estaremos agrupando países con el mismo perfil en los indicadores, sin importar el nivel. En cambio, para las distancias euclidiana o Manhattan, lo importante es la diferencia en los niveles.

Recordemos además que la distancia euclidiana computa desvíos cuadráticos, mientras que Manhattan usa desvíos absolutos. Por lo tanto, la distancia euclidiana penaliza grandes diferencias relativamente más que la distancia Manhattan.

Por otra parte, vemos que las distancias pueden estar potencialmente impulsadas, para algunos pares de observaciones, por solo alguna/s variable/s muy asimétricas con outliers brutos (en este caso, la densidad y la población). Si los datos son correctos, esto no es necesariamente malo y a priori no requiere ninguna corrección.

Sin embargo, una posible estrategia puede ser transformar estas variables con logaritmo antes de normalizarlas. El resultado es que los outliers no pesen tanto en el cálculo de las distancias. Hacer esto implica suponer que, para las variables transformadas, las diferencias que interesan son en el orden de magnitud, no en la escala original de la variable.

También podemos hacer un análisis más detallado de las distancias entre todos los pares de países.

# matriz de distancias
dist_obj = dist(dat_c, method="manhattan")
dist_matrix = as.matrix(dist_obj)
# nombres de filas y columnas
dimnames(dist_matrix) = list(country1=dat$country, country2=dat$country)
# de matriz a data.frame long con un atajo
dist_df = as.data.frame(as.table(dist_matrix)) %>%
  rename(dist = Freq) 

Veamos los países más cercanos y lejanos de Argentina.

tmp = dist_df %>% 
  filter(country1 != country2) %>% 
  filter(country1 == "Argentina") %>% 
  arrange(dist)

head(tmp)
NA
tail(tmp)
NA

Con estos datos podemos verificar visualmente si existen algunos países claramente atípicos (muy distantes del resto).

# distancia mediana de cada pais vs el resto
gdat = dist_df %>% 
  group_by(country1) %>%
  summarise(median_dist = median(dist))
# plot de las medianas ordenadas
plt = 
  ggplot(gdat, aes(x=reorder(country1, median_dist), y=median_dist)) +
  geom_point() +
  theme_minimal() +
  theme(axis.text.x=element_blank())

ggplotly(plt, width=860, height=450) 

### o con un boxplot por pais:
# ggplot(dist_df, aes(x=reorder(country1, dist, mean), y=dist)) + 
#   geom_boxplot() +
#   theme_minimal() +
#   theme(axis.text.x=element_text(angle=-90))
###

Efectivamente algunos países son potencialmente outliers; es decir, son muy distintos del resto, tienen pocos “vecinos” (países parecidos).

Clustering jerárquico

Vamos a ejecutar un algoritmo de clustering aglomerativo usando average linkage.

rownames(dat_c) = dat$country
# clustering jerarquico sin "cortar" el dendrograma
hc = amap::hcluster(dat_c, method="manhattan", link="average")

Dendrograma

Visualizamos los resultados con un dendrograma horizontal.

# identificamos algunos paises para colorearlos
grupos = ifelse(dat$country[hc$order] %in% "Argentina", 2, 1)
colores = c("black", "red")
# plot dendrograma
fviz_dend(hc, horiz=T, k_colors=colores, label_cols=grupos)

También podemos visualizar la estructura del dendrograma con un mapa de calor. Cada celda indica la distancia entre pares de países. Los países se ordenan según el dendrograma generado por el clustering jerárquico.

# matriz de distancias long con paises como factores
gdat = dist_df %>% 
  mutate(
    country1 = factor(country1, levels=dat$country[hc$order])
    ,country2 = factor(country2, levels=dat$country[hc$order])
  )

# funcion para heatmap (geom_tile)
mapacalor = function(long_df) {
  ggplot(long_df, aes(x=country1, y=country2, z=dist)) +
    geom_tile(aes(fill=dist)) +
    theme(
      axis.title.x=element_blank()
      ,axis.text.x=element_blank()
      ,axis.title.y=element_blank()
      ,axis.text.y=element_blank()
    ) +
    scale_fill_viridis_c()
} 

print( mapacalor(gdat) ) 

# lo mismo pero sin outliers
outlier_countries = c("India","China","Singapore")
gdat_sin_outliers = gdat %>% 
  filter(
    !(country1 %in% outlier_countries | country2 %in% outlier_countries)
  )

print( mapacalor(gdat_sin_outliers) ) 

Analizamos cuál puede ser una cantidad de clusters de países razonable según varios criterios.

Punto de quiebre

Un criterio posible es elegir el K a partir del cual se reduce significativamente la tasa de caída en la variabilidad intracluster.

fviz_nbclust(dat_c, FUNcluster=hcut, method="wss", k.max=20
             ,diss=dist(dat_c, method="manhattan"), hc_method="average") 

Silhouette

Otra posibilidad es mirar el silhouette promedio de todas las observaciones. El silhouette de cada objeto compara la cercanía con los objetos del propio cluster (cohesión) con la distancia a objetos de otros clusters (separación). El estadístico varía entre 1 y -1.

fviz_nbclust(dat_c, FUNcluster=hcut, method="silhouette", k.max=20
             ,diss=dist(dat_c, method="manhattan"), hc_method="average") 

Análisis de resultados

Supongamos que definimos \(K=17\), sabiendo que muchos de los clusters probablemente tengan tamaño=1 (“outliers”).

rownames(dat_c) = dat$country
# clustering jerarquico "cortado" en 17
hc = hcut(dat_c, k=17, hc_method="average", hc_metric="manhattan", stand=F)

Veamos el gráfico de silhouette para \(K=17\):

plt = 
  fviz_silhouette(hc, label=T, print.summary=F) +
  theme(axis.text.x=element_text(angle=-90, size=4))

print( plt )

Graficamos nuevamente un dendrograma horizontal pero coloreando por cluster.

fviz_dend(hc, horiz=T, k=17, repel=T) 

Otra forma de presentar el dendrograma es un árbol filogenético para facilitar la visualización. La disposición de cada objeto en el plano va a estar definida por algoritmos del campo de la teoría de grafos y comunidades.

fviz_dend(hc, type="phylogenic", k=17, repel=T) 

Añadimos a los datasets la pertenencia de cada objeto a cada grupo. También generamos una variable indicadora de “outlier”.

# data con variables originales
dat_hc = dat %>%
  mutate(cluster = factor(hc$cluster))

# indicamos "outliers"
outlier_countries = dat_hc %>% 
  group_by(cluster) %>% 
  filter(n() == 1) %>% 
  pull(country)
# indicador de outlier
dat_hc = dat_hc %>% 
  mutate(outlier = ifelse(country %in% outlier_countries, 1, 0))

# variables normalizadas
dat_c_hc = dat_c %>%
  bind_cols(dat %>% select(all_of(id_cols))) %>% 
  mutate(
    cluster = factor(hc$cluster)
    ,outlier = ifelse(country %in% outlier_countries, 1, 0)
  )

Comparamos visualmente las distribuciones de las variables entre clusters.

# long data.frame con variables normalizadas
gdat = dat_c_hc %>% 
  filter(outlier == 0) %>% 
  select(-outlier) %>% 
  pivot_longer(
    -all_of(c(id_cols, "cluster")), names_to="variable", values_to="value")
# densidades por variable
plt_density = 
  ggplot(gdat, aes(x=value, y=variable, color=cluster, point_color=cluster
                 , fill=cluster)) +
  ggridges::geom_density_ridges(
    alpha=0.5, scale=1
    ,jittered_points=T, position=position_points_jitter(height=0)
    ,point_shape="|", point_size=2
  ) +
  theme_minimal() +
  NULL

print(plt_density)

# boxplots por cluster
plt_boxplot =
  ggplot(gdat, aes(x=variable, y=value, color=cluster)) +
  facet_wrap(~cluster, ncol=2, scales="free_y") +
  geom_boxplot() +
  theme_minimal() +
  theme(axis.text.x=element_text(angle=-90)) +
  NULL

print(plt_boxplot)

Por último, representamos los clusters en un mapa:

# datos con info geografica
gdat = dat_sf %>% 
  left_join(dat_hc, by="iso3c") %>% 
  filter(iso3c != "ATA") %>% # sin antartica
  mutate(
    cluster = ifelse(outlier == 1, "outlier", cluster)
  )
# mapa
plt = 
  ggplot(gdat, aes(fill=cluster, label=country)) +
  geom_sf() +
  theme_minimal() +
  theme(legend.position="bottom") +
  NULL

ggplotly( plt, width=800 )

Extras

Test de Hopkins

Evaluamos si existe tendencia al agrupamiento usando el test de Hopkins.

hopkins = factoextra::get_clust_tendency(dat_c, n=100, seed=321)

cat("Hopkins =", hopkins$hopkins_stat)
Hopkins = 0.94469

Según la documentación de la función get_clust_tendency(), un Hopkins más alto indica mayor tendencia al clustering. En este caso, el valor del estadístico es evidentemente superior a 0.5, entonces podemos concluir que los países no están distribuidos uniformemente en el espacio de las variables. Es decir, presentan una tendencia a agruparse.

Gap statistic

Una forma de formalizar el criterio de “punto de quiebre” es el Gap statistic. Éste calcula la diferencia logarítmica entre la variabilidad intra-cluster del dataset real y datasets simulados con distribución uniforme.

set.seed(321)
fviz_nbclust(dat_c, FUNcluster=hcut, method="gap_stat", k.max=20
             ,nstart=50, nboot=100
             ,diss=dist(dat_c, method="manhattan"), hc_method="average")
Clustering k = 1,2,..., K.max (= 20): .. done
Bootstrapping, b = 1,2,..., B (= 100)  [one "." per sample]:
.................................................. 50 
.................................................. 100 

El criterio indica que se debe elegir el mínimo K a partir del cual la “tasa de creciemiento” del estadístico se reduce. Sin embargo, en presencia de outliers y subclusters con distintos grados de separación, el comportamiento es no monótono, por lo cual es necesario mirar toda la curva. Para más detalles ver el paper original.

LS0tDQp0aXRsZTogIkFwbGljYWNpb25lcyBkZSBjbHVzdGVyaW5nIg0KbGFuZzogZXMNCm91dHB1dDoNCiAgaHRtbF9ub3RlYm9vazoNCiAgICBoaWdobGlnaHQ6IHRhbmdvDQogICAgdGhlbWU6IGNvc21vDQogICAgdG9jOiB5ZXMNCiAgICB0b2NfZmxvYXQ6IHllcw0KICAgIHRvY19kZXB0aDogMg0KLS0tDQoNCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQ0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KA0KICB3YXJuaW5nPUYsIG1lc3NhZ2U9RiwgZWNobz1ULCBmaWcuYWxpZ249ImNlbnRlciIsIGZpZy53aWR0aD0xMCkNCmBgYA0KDQpgYGB7ciBsaWJzLCB3YXJuaW5nPUYsIG1lc3NhZ2U9Rn0NCnN1cHByZXNzUGFja2FnZVN0YXJ0dXBNZXNzYWdlcyh7DQogIGxpYnJhcnkodGlkeXZlcnNlKQ0KICBsaWJyYXJ5KGdsdWUpDQogIGxpYnJhcnkoR0dhbGx5KQ0KICBsaWJyYXJ5KGdncmlkZ2VzKQ0KICBsaWJyYXJ5KHBsb3RseSkNCiAgbGlicmFyeShmYWN0b2V4dHJhKQ0KICBsaWJyYXJ5KGFtYXApDQogIGxpYnJhcnkoc2YpDQogIGxpYnJhcnkoaWdyYXBoKQ0KICAjIHJlbW90ZXM6Omluc3RhbGxfZ2l0aHViKCJycGtncy9nZy5sYXllcnMiKQ0KICBsaWJyYXJ5KGdnLmxheWVycykNCn0pDQpgYGANCg0KIyBEYXRvcw0KDQpMZWVtb3MgbG9zIGRhdG9zIGRlbCBCYW5jbyBNdW5kaWFsIGNvbiBpbmRpY2Fkb3JlcyBwb3IgcGHDrXNlcyBxdWUgc2UgZW5jdWVudHJhbiBlbiBgZGF0YS93b3JsZGJhbmsuY3N2YC4gRW4gYGRhdGEvd29ybGRfYmFua21ldGFkYXRhLmNzdmAgcG9kZW1vcyByZXZpc2FyIGxvcyBtZXRhZGF0b3MgZGUgY2FkYSBpbmRpY2Fkb3IuIGBkYXRhL3dvcmxkYmFua19zZi5yZHNgIGNvbnRpZW5lIGxvcyBkYXRvcyBuZWNlc2FyaW9zIHBhcmEgaGFjZXIgbWFwYXMuDQoNCmBgYHtyIGRhdGF9DQpkYXQgPSByZWFkX2NzdigiZGF0YS93b3JsZGJhbmsuY3N2IikNCmRhdF9zZiA9IHJlYWRSRFMoImRhdGEvd29ybGRiYW5rX3NmLnJkcyIpDQoNCmBgYA0KDQojIEFuw6FsaXNpcyBleHBsb3JhdG9yaW8gSQ0KDQpFY2hhbW9zIHVuIHZpc3Rhem8gYSBsb3MgZGF0b3MuDQoNCmBgYHtyfQ0KZGltKGRhdCkNCg0KYGBgDQoNCmBgYHtyfQ0KbmFtZXMoZGF0KQ0KDQpgYGANCg0KYGBge3J9DQpoZWFkKGRhdCkNCg0KYGBgDQoNCkRlc2NhcnRhbW9zIHZhcmlhYmxlcyBpcnJlbGV2YW50ZXMuDQoNCmBgYHtyfQ0KZGF0ID0gZGF0ICU+JSBzZWxlY3QoLWMoZGF0ZSkpICMgZGVzY2FydGFtb3MgZWwgYcOxbw0KDQpgYGANCg0KVmVtb3MgbG9zIHBhw61zZXMgY29uIGxvcyB2YWxvcmVzIG3DoXMgYmFqb3MgeSBtw6FzIGFsdG9zIHBvciB2YXJpYWJsZQ0KDQpgYGB7cn0NCiMgdmFyaWFibGVzIGRlICJJRCIgKHkgcXVlIG5vIHNpcnZlbiBwYXJhIGFncnVwYXIpDQppZF9jb2xzID0gYygiaXNvM2MiLCAiY291bnRyeSIsICJyZWdpb24iLCAiaW5jb21lX2xldmVsIikNCmRhdF90bXAgPSBkYXQgJT4lIA0KICAjIGZvcm1hdG8gbG9uZw0KICBwaXZvdF9sb25nZXIoLWFsbF9vZihpZF9jb2xzKSwgbmFtZXNfdG89InZhcmlhYmxlIiwgdmFsdWVzX3RvPSJ2YWx1ZSIpICU+JSANCiAgYXJyYW5nZSh2YXJpYWJsZSkgJT4lIA0KICBzZWxlY3QoLWlzbzNjLCAtcmVnaW9uLCAtaW5jb21lX2xldmVsKSAlPiUgDQogICMgdmFsb3JlcyBvcmRlbmFkb3MgcG9yIHZhcmlhYmxlDQogIGdyb3VwX2J5KHZhcmlhYmxlKSAlPiUgDQogIGFycmFuZ2UoLXZhbHVlKSANCiMgZGF0YS5mcmFtZSBjb24gdG9wMyB5IGJvdHRvbTMgcG9yIHZhcmlhYmxlDQpyZG8gPSBiaW5kX3Jvd3MoDQogIGRhdF90bXAgJT4lIHRvcF9uKDMsIHZhbHVlKSAlPiUgdW5ncm91cCgpDQogICxkYXRfdG1wICU+JSB0b3BfbigtMywgdmFsdWUpICU+JSB1bmdyb3VwKCkNCikgJT4lIA0KICBhcnJhbmdlKHZhcmlhYmxlLCB2YWx1ZSkNCg0KIyBwcmludDogdW4gZGF0YWZyYW1lIHBvciBjYWRhIHZhcmlhYmxlDQpwcmludCggc3BsaXQocmRvLCByZG8kdmFyaWFibGUpICkNCg0KIyMjIGFsdGVybmF0aXZhOg0KIyBmb3IgKHZhcl8gaW4gbmFtZXMoZGF0KSkgew0KIyAgIHRtcCA9IGRhdCAlPiUgDQojICAgICBhcnJhbmdlKCEhc3ltKHZhcl8pKSAlPiUgDQojICAgICBzZWxlY3QoY291bnRyeSwgdmFyXykNCiMgICB0b3AgPSB0bXAgJT4lIGhlYWQoMykNCiMgICBib3R0b20gPSB0bXAgJT4lIHRhaWwoMykNCiMgICBwcmludCh2YXJfKQ0KIyAgIHByaW50KGJpbmRfcm93cyh0b3AsIGJvdHRvbSkpDQojIH0NCiMjIw0KDQpgYGANCg0KR3JhZmljYW1vcyBsYSBkaXN0cmlidWNpw7NuIGRlIGNhZGEgdmFyaWFibGUgcG9yIHNlcGFyYWRvOg0KDQpgYGB7cn0NCiMgZm9ybWF0byBsb25nDQpnZGF0ID0gZGF0ICU+JQ0KICBwaXZvdF9sb25nZXIoLWFsbF9vZihpZF9jb2xzKSwgbmFtZXNfdG89InZhcmlhYmxlIiwgdmFsdWVzX3RvPSJ2YWx1ZSIpDQojIHBsb3QgZGUgZGVuc2lkYWQgcG9yIHZhcmlhYmxlDQpwbHQgPSANCiAgZ2dwbG90KGdkYXQpICsNCiAgZ2VvbV9kZW5zaXR5KGFlcyh4PXZhbHVlKSwgZmlsbD0icmVkIiwgYWxwaGE9MC4yKSArDQogIGZhY2V0X3dyYXAofnZhcmlhYmxlLCBzY2FsZXMgPSAiZnJlZSIpICsNCiAgdGhlbWVfbWluaW1hbCgpICsNCiAgTlVMTA0KDQpwcmludChwbHQpDQoNCmBgYA0KDQpBbmFsaXphbW9zIGxhcyBjb3JyZWxhY2lvbmVzIGVudHJlIGxhcyB2YXJpYWJsZXM6DQoNCmBgYHtyIGNvcnJ9DQojIGRhdGFmcmFtZSBjb24gdmFyaWFibGVzIG51bWVyaWNhcw0KZGF0X251bSA9IGRhdCAlPiUgc2VsZWN0X2lmKGlzLm51bWVyaWMpDQojIG1hdHJpeiBkZSBjb3JyZWxhY2lvbmVzIGNvbW8gcGxvdA0KcGx0ID0gR0dhbGx5OjpnZ2NvcnIoZGF0X251bSwgbGFiZWw9VCwgbWV0aG9kPWMoImFsbC5vYnMiLCJzcGVhcm1hbiIpKQ0KDQpwcmludCggcGx0ICkNCg0KIyMjIG9wY2lvbiBpbnRlcmVzYW50ZSBwYXJhIGdyYWZpY2FyOg0KIyBHR2FsbHk6OmdncGFpcnMoKQ0KDQpgYGANCg0KIyBQcmVwcm9jZXNhbWllbnRvDQoNCkNyZWFtb3MgdW4gZGF0YS5mcmFtZSBjb24gbGFzIHZhcmlhYmxlcyBxdWUgdXNhcmVtb3MgcGFyYSBhZ3J1cGFyIHBhw61zZXMuDQoNClZhbW9zIGEgKipub3JtYWxpemFyKiogZXN0YXMgdmFyaWFibGVzIHBhcmEgcXVlIGVzdMOpbiBlbiAqKmVzY2FsYXMgY29tcGFyYWJsZXMqKi4gRXN0ZSBwYXNvIHNlIGNvbm9jZSBjb21vICpzY2FsaW5nKi4gTGFzIG5vcm1hbGl6YWNpb25lcyBtw6FzIGNvbXVuZXMgc29uOg0KDQotICAgZXN0YW5kYXJpemFjacOzbiAqKm1lZGlhLWRlc3bDrW8qKg0KDQokJCBcZnJhY3t4IC0gYXZnKHgpfXtzZCh4KX0gJCQNCg0KVG9kYXMgbGFzIHZhcmlhYmxlcyBxdWVkYW4gY29uIG1lZGlhIDAgeSBkZXN2w61vIDEsIHkgbGFzIHVuaWRhZGVzIHJlcHJlc2VudGFuIGRlc3bDrW9zIGNvbiByZXNwZWN0byBhIGxhIG1lZGlhLiBMYXMgdmFyaWFibGVzIGNvbiBtw6FzIHZhbG9yZXMgZXh0cmVtb3MgdGVuZHLDoW4gdW4gcmFuZ28gbcOhcyBhbHRvIHF1ZSBlbCByZXN0by4NCg0KLSAgICoqbWluLW1heCoqDQoNCiQkIFxmcmFje3ggLSBtaW4oeCl9e21heCh4KSAtIG1pbih4KX0gJCQgVG9kYXMgbGFzIHZhcmlhYmxlcyBxdWVkYW4gZXhwcmVzYWRhcyBlbiBlbCByYW5nbyAwLTEuIExhcyBtZWRpYXMgeSBsb3MgZGVzdsOtb3MgZGUgbGFzIHZhcmlhYmxlcyBubyBzb24gaWd1YWxlcywgYSBkaWZlcmVuY2lhIGRlIGxhIGVzdGFuZGFyaXphY2nDs24gY29udmVuY2lvbmFsLg0KDQotICAgZXN0YW5kYXJpemFjacOzbiAqKnJvYnVzdGEqKg0KDQokJCBcZnJhY3t4IC0gbWVkaWFuKHgpfXtJUVIoeCl9ICQkDQoNCkVuIGx1Z2FyIGRlIHVzYXIgbGEgbWVkaWEgeSBsYSB2YXJpYW56YSwgc2UgdXNhIGxhIG1lZGlhbmEgeSBlbCByYW5nbyBpbnRlcmN1YXJ0w61saWNvLiBFc3RlIHRpcG8gZGUgbm9ybWFsaXphY2nDs24gZXMgcm9idXN0YSBhIHZhbG9yZXMgZXh0cmVtb3MgcG9yIHZhcmlhYmxlLg0KDQpgYGB7ciBub3JtYWxpemF9DQojIGZ1bmNpb25lcyAodWRmKSBwYXJhIG5vcm1hbGl6YXINCm1pbm1heCA9IGZ1bmN0aW9uKHgpICh4IC0gbWluKHgpKSAvIChtYXgoeCkgLSBtaW4oeCkpDQpyb2Jfc2NhbGUgPSBmdW5jdGlvbih4KSAoeCAtIG1lZGlhbih4KSkgLyBJUVIoeCkNCiMgZGF0YSBudW1lcmljYSBub3JtYWxpemFkYQ0KZGF0X2MgPSBkYXQgJT4lDQogIHNlbGVjdF9pZihpcy5udW1lcmljKSAlPiUgDQogICMgc2NhbGUoY2VudGVyPVQsIHNjYWxlPVQpICU+JSAjIGVzdGFuZGFyaXphY2lvbiBtZWRpYS1kZXN2aW8NCiAgbXV0YXRlX2FsbChyb2Jfc2NhbGUpICU+JSAjIG5vcm1hbGl6YWNpb24NCiAgYXMuZGF0YS5mcmFtZSgpICMgbGFzIGZ1bmNpb25lcyBkZSBjbHVzdGVyIHNlIGxsZXZhbiBtZWpvciBjb24gZGF0YS5mcmFtZSAoYWRtaXRlIHJvdy5uYW1lcykNCg0KYGBgDQoNCiMgQW7DoWxpc2lzIGV4cGxvcmF0b3JpbyBJSQ0KDQpBbmFsaXphbW9zIGxvcyAqcGVyZmlsZXMqIGRlIGxvcyBwYcOtc2VzIGVuIHTDqXJtaW5vcyBkZSBsYXMgdmFyaWFibGVzLiBFc3RlIGdyw6FmaWNvIG5vcyBwdWVkZSBzZXJ2aXIgcGFyYSBkZWZpbmlyIGxhIG5vY2nDs24gZGUgKipzaW1pbGl0dWQvZGlzaW1pbGl0dWQqKiBhcHJvcGlhZGEgcGFyYSBudWVzdHJvIHByb2JsZW1hLg0KDQpgYGB7ciBwYXJhbGxlbH0NCiMgZm9ybWF0byBsb25nIGNvbiBkYXRvcyBub3JtYWxpemFkb3MNCmdkYXQgPSBkYXQgJT4lDQogIG11dGF0ZV9pZihpcy5udW1lcmljLCByb2Jfc2NhbGUpICU+JSANCiAgcGl2b3RfbG9uZ2VyKA0KICAgIC1hbGxfb2YoaWRfY29scyksIG5hbWVzX3RvPSJ2YXJpYWJsZSIsIHZhbHVlc190bz0idmFsdWUiDQogICkNCiMgcGxvdCBkZSBjb29yZGVuYWRhcyBwYXJhbGVsYXMNCnBsdCA9IGdncGxvdChnZGF0LCBhZXMoeD12YXJpYWJsZSwgeT12YWx1ZSwgZ3JvdXA9Y291bnRyeSkpICsNCiAgZ2VvbV9saW5lKGFscGhhPTAuMykgKw0KICBnZW9tX2xpbmUoZGF0YT1maWx0ZXIoZ2RhdCwgY291bnRyeT09IkFyZ2VudGluYSIpDQogICAgICAgICAgICAsIGNvbG9yPSJyZWQiLCBhbHBoYT0wLjMpICsNCiAgdGhlbWVfbWluaW1hbCgpDQoNCiMgcGxvdCBpbnRlcmFjdGl2bw0KZ2dwbG90bHkocGx0LCB3aWR0aD04NjAsIGhlaWdodD01MDApDQoNCmBgYA0KDQpgYGB7cn0NCiMgbG8gbWlzbW8gcGVybyBzaW4gb3V0bGllcnMuLi4NCmdkYXRfc2luX291dGxpZXJzID0gZ2RhdCAlPiUgDQogIGZpbHRlcighY291bnRyeSAlaW4lIGMoIkluZGlhIiwiQ2hpbmEiLCJTaW5nYXBvcmUiKSkNCnBsdF9zaW5fb3V0bGllcnMgPSANCiAgZ2dwbG90KGdkYXRfc2luX291dGxpZXJzLCBhZXMoeD12YXJpYWJsZSwgeT12YWx1ZSwgZ3JvdXA9Y291bnRyeSkpICsNCiAgZ2VvbV9saW5lKGFscGhhPTAuMykgKw0KICBnZW9tX2xpbmUoZGF0YT1maWx0ZXIoZ2RhdCwgY291bnRyeT09IkFyZ2VudGluYSIpDQogICAgICAgICAgICAsIGNvbG9yPSJyZWQiLCBhbHBoYT0wLjMpICsNCiAgdGhlbWVfbWluaW1hbCgpDQoNCmdncGxvdGx5KHBsdF9zaW5fb3V0bGllcnMsIHdpZHRoPTg2MCwgaGVpZ2h0PTUwMCkNCg0KIyMjIGFsdGVybmF0aXZhOg0KIyBHR2FsbHk6OmdncGFyY29vcmQoKQ0KIyMjDQoNCmBgYA0KDQpQb3IgZWplbXBsbywgc2kgdXNhbW9zIGxhIGRpc2ltaWxpdHVkIGRlICoqY29ycmVsYWNpw7NuKiogY29tbyBtw6l0cmljYSwgZXN0YXJlbW9zIGFncnVwYW5kbyBwYcOtc2VzIGNvbiBlbCBtaXNtbyAqKnBlcmZpbCoqIGVuIGxvcyBpbmRpY2Fkb3Jlcywgc2luIGltcG9ydGFyIGVsIG5pdmVsLiBFbiBjYW1iaW8sIHBhcmEgbGFzIGRpc3RhbmNpYXMgKipldWNsaWRpYW5hKiogbyAqKk1hbmhhdHRhbioqLCBsbyBpbXBvcnRhbnRlIGVzIGxhIGRpZmVyZW5jaWEgZW4gbG9zICoqbml2ZWxlcyoqLg0KDQpSZWNvcmRlbW9zIGFkZW3DoXMgcXVlIGxhIGRpc3RhbmNpYSBldWNsaWRpYW5hIGNvbXB1dGEgKipkZXN2w61vcyBjdWFkcsOhdGljb3MqKiwgbWllbnRyYXMgcXVlIE1hbmhhdHRhbiB1c2EgKipkZXN2w61vcyBhYnNvbHV0b3MqKi4gUG9yIGxvIHRhbnRvLCBsYSBkaXN0YW5jaWEgZXVjbGlkaWFuYSBwZW5hbGl6YSBncmFuZGVzIGRpZmVyZW5jaWFzIHJlbGF0aXZhbWVudGUgbcOhcyBxdWUgbGEgZGlzdGFuY2lhIE1hbmhhdHRhbi4NCg0KUG9yIG90cmEgcGFydGUsIHZlbW9zIHF1ZSBsYXMgZGlzdGFuY2lhcyBwdWVkZW4gZXN0YXIgcG90ZW5jaWFsbWVudGUgaW1wdWxzYWRhcywgcGFyYSBhbGd1bm9zIHBhcmVzIGRlIG9ic2VydmFjaW9uZXMsIHBvciBzb2xvIGFsZ3VuYS9zIHZhcmlhYmxlL3MgbXV5IGFzaW3DqXRyaWNhcyBjb24gb3V0bGllcnMgYnJ1dG9zIChlbiBlc3RlIGNhc28sIGxhIGRlbnNpZGFkIHkgbGEgcG9ibGFjacOzbikuIFNpIGxvcyBkYXRvcyBzb24gY29ycmVjdG9zLCBlc3RvIG5vIGVzIG5lY2VzYXJpYW1lbnRlIG1hbG8geSBfYSBwcmlvcmlfIG5vIHJlcXVpZXJlIG5pbmd1bmEgY29ycmVjY2nDs24uIA0KDQpTaW4gZW1iYXJnbywgdW5hIHBvc2libGUgZXN0cmF0ZWdpYSBwdWVkZSBzZXIgdHJhbnNmb3JtYXIgZXN0YXMgdmFyaWFibGVzIGNvbiAqKmxvZ2FyaXRtbyoqIGFudGVzIGRlIG5vcm1hbGl6YXJsYXMuIEVsIHJlc3VsdGFkbyBlcyBxdWUgbG9zIG91dGxpZXJzIG5vIHBlc2VuIHRhbnRvIGVuIGVsIGPDoWxjdWxvIGRlIGxhcyBkaXN0YW5jaWFzLiBIYWNlciBlc3RvIGltcGxpY2Egc3Vwb25lciBxdWUsIHBhcmEgbGFzIHZhcmlhYmxlcyB0cmFuc2Zvcm1hZGFzLCBsYXMgZGlmZXJlbmNpYXMgcXVlIGludGVyZXNhbiBzb24gZW4gZWwgKipvcmRlbiBkZSBtYWduaXR1ZCoqLCBubyBlbiBsYSBlc2NhbGEgb3JpZ2luYWwgZGUgbGEgdmFyaWFibGUuDQoNClRhbWJpw6luIHBvZGVtb3MgaGFjZXIgdW4gYW7DoWxpc2lzIG3DoXMgZGV0YWxsYWRvIGRlIGxhcyBkaXN0YW5jaWFzIGVudHJlIHRvZG9zIGxvcyBwYXJlcyBkZSBwYcOtc2VzLg0KDQpgYGB7ciBkaXN0fQ0KIyBtYXRyaXogZGUgZGlzdGFuY2lhcw0KZGlzdF9vYmogPSBkaXN0KGRhdF9jLCBtZXRob2Q9Im1hbmhhdHRhbiIpDQpkaXN0X21hdHJpeCA9IGFzLm1hdHJpeChkaXN0X29iaikNCiMgbm9tYnJlcyBkZSBmaWxhcyB5IGNvbHVtbmFzDQpkaW1uYW1lcyhkaXN0X21hdHJpeCkgPSBsaXN0KGNvdW50cnkxPWRhdCRjb3VudHJ5LCBjb3VudHJ5Mj1kYXQkY291bnRyeSkNCiMgZGUgbWF0cml6IGEgZGF0YS5mcmFtZSBsb25nIGNvbiB1biBhdGFqbw0KZGlzdF9kZiA9IGFzLmRhdGEuZnJhbWUoYXMudGFibGUoZGlzdF9tYXRyaXgpKSAlPiUNCiAgcmVuYW1lKGRpc3QgPSBGcmVxKSANCg0KYGBgDQoNClZlYW1vcyBsb3MgcGHDrXNlcyBtw6FzIGNlcmNhbm9zIHkgbGVqYW5vcyBkZSBBcmdlbnRpbmEuDQoNCmBgYHtyfQ0KdG1wID0gZGlzdF9kZiAlPiUgDQogIGZpbHRlcihjb3VudHJ5MSAhPSBjb3VudHJ5MikgJT4lIA0KICBmaWx0ZXIoY291bnRyeTEgPT0gIkFyZ2VudGluYSIpICU+JSANCiAgYXJyYW5nZShkaXN0KQ0KDQpoZWFkKHRtcCkNCg0KYGBgDQoNCmBgYHtyfQ0KdGFpbCh0bXApDQoNCmBgYA0KDQpDb24gZXN0b3MgZGF0b3MgcG9kZW1vcyB2ZXJpZmljYXIgdmlzdWFsbWVudGUgc2kgZXhpc3RlbiBhbGd1bm9zIHBhw61zZXMgY2xhcmFtZW50ZSBhdMOtcGljb3MgKG11eSBkaXN0YW50ZXMgZGVsIHJlc3RvKS4NCg0KYGBge3J9DQojIGRpc3RhbmNpYSBtZWRpYW5hIGRlIGNhZGEgcGFpcyB2cyBlbCByZXN0bw0KZ2RhdCA9IGRpc3RfZGYgJT4lIA0KICBncm91cF9ieShjb3VudHJ5MSkgJT4lDQogIHN1bW1hcmlzZShtZWRpYW5fZGlzdCA9IG1lZGlhbihkaXN0KSkNCiMgcGxvdCBkZSBsYXMgbWVkaWFuYXMgb3JkZW5hZGFzDQpwbHQgPSANCiAgZ2dwbG90KGdkYXQsIGFlcyh4PXJlb3JkZXIoY291bnRyeTEsIG1lZGlhbl9kaXN0KSwgeT1tZWRpYW5fZGlzdCkpICsNCiAgZ2VvbV9wb2ludCgpICsNCiAgdGhlbWVfbWluaW1hbCgpICsNCiAgdGhlbWUoYXhpcy50ZXh0Lng9ZWxlbWVudF9ibGFuaygpKQ0KDQpnZ3Bsb3RseShwbHQsIHdpZHRoPTg2MCwgaGVpZ2h0PTQ1MCkgDQoNCiMjIyBvIGNvbiB1biBib3hwbG90IHBvciBwYWlzOg0KIyBnZ3Bsb3QoZGlzdF9kZiwgYWVzKHg9cmVvcmRlcihjb3VudHJ5MSwgZGlzdCwgbWVhbiksIHk9ZGlzdCkpICsgDQojICAgZ2VvbV9ib3hwbG90KCkgKw0KIyAgIHRoZW1lX21pbmltYWwoKSArDQojICAgdGhlbWUoYXhpcy50ZXh0Lng9ZWxlbWVudF90ZXh0KGFuZ2xlPS05MCkpDQojIyMNCg0KYGBgDQoNCkVmZWN0aXZhbWVudGUgYWxndW5vcyBwYcOtc2VzIHNvbiBwb3RlbmNpYWxtZW50ZSBvdXRsaWVyczsgZXMgZGVjaXIsIHNvbiBtdXkgZGlzdGludG9zIGRlbCByZXN0bywgdGllbmVuIHBvY29zICJ2ZWNpbm9zIiAocGHDrXNlcyBwYXJlY2lkb3MpLg0KDQojIENsdXN0ZXJpbmcgamVyw6FycXVpY28NCg0KVmFtb3MgYSBlamVjdXRhciB1biBhbGdvcml0bW8gZGUgKipjbHVzdGVyaW5nIGFnbG9tZXJhdGl2byoqIHVzYW5kbyAqYXZlcmFnZSBsaW5rYWdlKi4NCg0KYGBge3J9DQpyb3duYW1lcyhkYXRfYykgPSBkYXQkY291bnRyeQ0KIyBjbHVzdGVyaW5nIGplcmFycXVpY28gc2luICJjb3J0YXIiIGVsIGRlbmRyb2dyYW1hDQpoYyA9IGFtYXA6OmhjbHVzdGVyKGRhdF9jLCBtZXRob2Q9Im1hbmhhdHRhbiIsIGxpbms9ImF2ZXJhZ2UiKQ0KYGBgDQoNCiMjIERlbmRyb2dyYW1hDQoNClZpc3VhbGl6YW1vcyBsb3MgcmVzdWx0YWRvcyBjb24gdW4gZGVuZHJvZ3JhbWEgaG9yaXpvbnRhbC4NCg0KYGBge3IgZGVuZHJvZ3JhbWEsIGZpZy5oZWlnaHQ9MTh9DQojIGlkZW50aWZpY2Ftb3MgYWxndW5vcyBwYWlzZXMgcGFyYSBjb2xvcmVhcmxvcw0KZ3J1cG9zID0gaWZlbHNlKGRhdCRjb3VudHJ5W2hjJG9yZGVyXSAlaW4lICJBcmdlbnRpbmEiLCAyLCAxKQ0KY29sb3JlcyA9IGMoImJsYWNrIiwgInJlZCIpDQojIHBsb3QgZGVuZHJvZ3JhbWENCmZ2aXpfZGVuZChoYywgaG9yaXo9VCwga19jb2xvcnM9Y29sb3JlcywgbGFiZWxfY29scz1ncnVwb3MpDQpgYGANCg0KVGFtYmnDqW4gcG9kZW1vcyB2aXN1YWxpemFyIGxhIGVzdHJ1Y3R1cmEgZGVsIGRlbmRyb2dyYW1hIGNvbiB1biAqKm1hcGEgZGUgY2Fsb3IqKi4gQ2FkYSBjZWxkYSBpbmRpY2EgbGEgZGlzdGFuY2lhIGVudHJlIHBhcmVzIGRlIHBhw61zZXMuIExvcyBwYcOtc2VzIHNlIG9yZGVuYW4gc2Vnw7puIGVsIGRlbmRyb2dyYW1hIGdlbmVyYWRvIHBvciBlbCBjbHVzdGVyaW5nIGplcsOhcnF1aWNvLg0KDQpgYGB7ciwgZmlnLndpZHRoPTcsIGZpZy5oZWlnaHQ9NH0NCiMgbWF0cml6IGRlIGRpc3RhbmNpYXMgbG9uZyBjb24gcGFpc2VzIGNvbW8gZmFjdG9yZXMNCmdkYXQgPSBkaXN0X2RmICU+JSANCiAgbXV0YXRlKA0KICAgIGNvdW50cnkxID0gZmFjdG9yKGNvdW50cnkxLCBsZXZlbHM9ZGF0JGNvdW50cnlbaGMkb3JkZXJdKQ0KICAgICxjb3VudHJ5MiA9IGZhY3Rvcihjb3VudHJ5MiwgbGV2ZWxzPWRhdCRjb3VudHJ5W2hjJG9yZGVyXSkNCiAgKQ0KDQojIGZ1bmNpb24gcGFyYSBoZWF0bWFwIChnZW9tX3RpbGUpDQptYXBhY2Fsb3IgPSBmdW5jdGlvbihsb25nX2RmKSB7DQogIGdncGxvdChsb25nX2RmLCBhZXMoeD1jb3VudHJ5MSwgeT1jb3VudHJ5Miwgej1kaXN0KSkgKw0KICAgIGdlb21fdGlsZShhZXMoZmlsbD1kaXN0KSkgKw0KICAgIHRoZW1lKA0KICAgICAgYXhpcy50aXRsZS54PWVsZW1lbnRfYmxhbmsoKQ0KICAgICAgLGF4aXMudGV4dC54PWVsZW1lbnRfYmxhbmsoKQ0KICAgICAgLGF4aXMudGl0bGUueT1lbGVtZW50X2JsYW5rKCkNCiAgICAgICxheGlzLnRleHQueT1lbGVtZW50X2JsYW5rKCkNCiAgICApICsNCiAgICBzY2FsZV9maWxsX3ZpcmlkaXNfYygpDQp9IA0KDQpwcmludCggbWFwYWNhbG9yKGdkYXQpICkgDQpgYGANCg0KYGBge3IsIGZpZy53aWR0aD03LCBmaWcuaGVpZ2h0PTR9DQojIGxvIG1pc21vIHBlcm8gc2luIG91dGxpZXJzDQpvdXRsaWVyX2NvdW50cmllcyA9IGMoIkluZGlhIiwiQ2hpbmEiLCJTaW5nYXBvcmUiKQ0KZ2RhdF9zaW5fb3V0bGllcnMgPSBnZGF0ICU+JSANCiAgZmlsdGVyKA0KICAgICEoY291bnRyeTEgJWluJSBvdXRsaWVyX2NvdW50cmllcyB8IGNvdW50cnkyICVpbiUgb3V0bGllcl9jb3VudHJpZXMpDQogICkNCg0KcHJpbnQoIG1hcGFjYWxvcihnZGF0X3Npbl9vdXRsaWVycykgKSANCg0KYGBgDQoNCkFuYWxpemFtb3MgY3XDoWwgcHVlZGUgc2VyIHVuYSBjYW50aWRhZCBkZSBjbHVzdGVycyBkZSBwYcOtc2VzIHJhem9uYWJsZSBzZWfDum4gdmFyaW9zIGNyaXRlcmlvcy4NCg0KIyMgUHVudG8gZGUgcXVpZWJyZQ0KDQpVbiBjcml0ZXJpbyBwb3NpYmxlIGVzIGVsZWdpciBlbCBLIGEgcGFydGlyIGRlbCBjdWFsIHNlIHJlZHVjZSBzaWduaWZpY2F0aXZhbWVudGUgbGEgdGFzYSBkZSBjYcOtZGEgZW4gbGEgKip2YXJpYWJpbGlkYWQgaW50cmFjbHVzdGVyKiouDQoNCmBgYHtyIH0NCmZ2aXpfbmJjbHVzdChkYXRfYywgRlVOY2x1c3Rlcj1oY3V0LCBtZXRob2Q9IndzcyIsIGsubWF4PTIwDQogICAgICAgICAgICAgLGRpc3M9ZGlzdChkYXRfYywgbWV0aG9kPSJtYW5oYXR0YW4iKSwgaGNfbWV0aG9kPSJhdmVyYWdlIikgDQpgYGANCg0KIyMgU2lsaG91ZXR0ZQ0KDQpPdHJhIHBvc2liaWxpZGFkIGVzIG1pcmFyIGVsICoqc2lsaG91ZXR0ZSoqIHByb21lZGlvIGRlIHRvZGFzIGxhcyBvYnNlcnZhY2lvbmVzLiBFbCBzaWxob3VldHRlIGRlIGNhZGEgb2JqZXRvIGNvbXBhcmEgbGEgY2VyY2Fuw61hIGNvbiBsb3Mgb2JqZXRvcyBkZWwgcHJvcGlvIGNsdXN0ZXIgKCoqY29oZXNpw7NuKiopIGNvbiBsYSBkaXN0YW5jaWEgYSBvYmpldG9zIGRlIG90cm9zIGNsdXN0ZXJzICgqKnNlcGFyYWNpw7NuKiopLiBFbCBlc3RhZMOtc3RpY28gdmFyw61hIGVudHJlIDEgeSAtMS4NCg0KYGBge3IgfQ0KZnZpel9uYmNsdXN0KGRhdF9jLCBGVU5jbHVzdGVyPWhjdXQsIG1ldGhvZD0ic2lsaG91ZXR0ZSIsIGsubWF4PTIwDQogICAgICAgICAgICAgLGRpc3M9ZGlzdChkYXRfYywgbWV0aG9kPSJtYW5oYXR0YW4iKSwgaGNfbWV0aG9kPSJhdmVyYWdlIikgDQpgYGANCg0KIyBBbsOhbGlzaXMgZGUgcmVzdWx0YWRvcw0KDQpTdXBvbmdhbW9zIHF1ZSBkZWZpbmltb3MgJEs9MTckLCBzYWJpZW5kbyBxdWUgbXVjaG9zIGRlIGxvcyBjbHVzdGVycyBwcm9iYWJsZW1lbnRlIHRlbmdhbiB0YW1hw7FvPTEgKCJvdXRsaWVycyIpLg0KDQpgYGB7cn0NCnJvd25hbWVzKGRhdF9jKSA9IGRhdCRjb3VudHJ5DQojIGNsdXN0ZXJpbmcgamVyYXJxdWljbyAiY29ydGFkbyIgZW4gMTcNCmhjID0gaGN1dChkYXRfYywgaz0xNywgaGNfbWV0aG9kPSJhdmVyYWdlIiwgaGNfbWV0cmljPSJtYW5oYXR0YW4iLCBzdGFuZD1GKQ0KDQpgYGANCg0KVmVhbW9zIGVsIGdyw6FmaWNvIGRlIHNpbGhvdWV0dGUgcGFyYSAkSz0xNyQ6DQoNCmBgYHtyLCBmaWcuaGVpZ2h0PTEyfQ0KcGx0ID0gDQogIGZ2aXpfc2lsaG91ZXR0ZShoYywgbGFiZWw9VCwgcHJpbnQuc3VtbWFyeT1GKSArDQogIHRoZW1lKGF4aXMudGV4dC54PWVsZW1lbnRfdGV4dChhbmdsZT0tOTAsIHNpemU9NCkpDQoNCnByaW50KCBwbHQgKQ0KDQpgYGANCg0KR3JhZmljYW1vcyBudWV2YW1lbnRlIHVuIGRlbmRyb2dyYW1hIGhvcml6b250YWwgcGVybyBjb2xvcmVhbmRvIHBvciBjbHVzdGVyLg0KDQpgYGB7ciBmaWcuaGVpZ2h0PTE4fQ0KZnZpel9kZW5kKGhjLCBob3Jpej1ULCBrPTE3LCByZXBlbD1UKSANCg0KYGBgDQoNCk90cmEgZm9ybWEgZGUgcHJlc2VudGFyIGVsIGRlbmRyb2dyYW1hIGVzIHVuIMOhcmJvbCBmaWxvZ2Vuw6l0aWNvIHBhcmEgZmFjaWxpdGFyIGxhIHZpc3VhbGl6YWNpw7NuLiBMYSBkaXNwb3NpY2nDs24gZGUgY2FkYSBvYmpldG8gZW4gZWwgcGxhbm8gdmEgYSBlc3RhciBkZWZpbmlkYSBwb3IgYWxnb3JpdG1vcyBkZWwgY2FtcG8gZGUgbGEgdGVvcsOtYSBkZSBncmFmb3MgeSBjb211bmlkYWRlcy4NCg0KYGBge3IsIGZpZy5oZWlnaHQ9OH0NCmZ2aXpfZGVuZChoYywgdHlwZT0icGh5bG9nZW5pYyIsIGs9MTcsIHJlcGVsPVQpIA0KDQpgYGANCg0KQcOxYWRpbW9zIGEgbG9zIGRhdGFzZXRzIGxhIHBlcnRlbmVuY2lhIGRlIGNhZGEgb2JqZXRvIGEgY2FkYSBncnVwby4gVGFtYmnDqW4gZ2VuZXJhbW9zIHVuYSB2YXJpYWJsZSBpbmRpY2Fkb3JhIGRlICJvdXRsaWVyIi4NCg0KYGBge3J9DQojIGRhdGEgY29uIHZhcmlhYmxlcyBvcmlnaW5hbGVzDQpkYXRfaGMgPSBkYXQgJT4lDQogIG11dGF0ZShjbHVzdGVyID0gZmFjdG9yKGhjJGNsdXN0ZXIpKQ0KDQojIGluZGljYW1vcyAib3V0bGllcnMiDQpvdXRsaWVyX2NvdW50cmllcyA9IGRhdF9oYyAlPiUgDQogIGdyb3VwX2J5KGNsdXN0ZXIpICU+JSANCiAgZmlsdGVyKG4oKSA9PSAxKSAlPiUgDQogIHB1bGwoY291bnRyeSkNCiMgaW5kaWNhZG9yIGRlIG91dGxpZXINCmRhdF9oYyA9IGRhdF9oYyAlPiUgDQogIG11dGF0ZShvdXRsaWVyID0gaWZlbHNlKGNvdW50cnkgJWluJSBvdXRsaWVyX2NvdW50cmllcywgMSwgMCkpDQoNCiMgdmFyaWFibGVzIG5vcm1hbGl6YWRhcw0KZGF0X2NfaGMgPSBkYXRfYyAlPiUNCiAgYmluZF9jb2xzKGRhdCAlPiUgc2VsZWN0KGFsbF9vZihpZF9jb2xzKSkpICU+JSANCiAgbXV0YXRlKA0KICAgIGNsdXN0ZXIgPSBmYWN0b3IoaGMkY2x1c3RlcikNCiAgICAsb3V0bGllciA9IGlmZWxzZShjb3VudHJ5ICVpbiUgb3V0bGllcl9jb3VudHJpZXMsIDEsIDApDQogICkNCg0KYGBgDQoNCkNvbXBhcmFtb3MgdmlzdWFsbWVudGUgbGFzIGRpc3RyaWJ1Y2lvbmVzIGRlIGxhcyB2YXJpYWJsZXMgZW50cmUgY2x1c3RlcnMuDQoNCmBgYHtyLCBmaWcuaGVpZ2h0PTh9DQojIGxvbmcgZGF0YS5mcmFtZSBjb24gdmFyaWFibGVzIG5vcm1hbGl6YWRhcw0KZ2RhdCA9IGRhdF9jX2hjICU+JSANCiAgZmlsdGVyKG91dGxpZXIgPT0gMCkgJT4lIA0KICBzZWxlY3QoLW91dGxpZXIpICU+JSANCiAgcGl2b3RfbG9uZ2VyKA0KICAgIC1hbGxfb2YoYyhpZF9jb2xzLCAiY2x1c3RlciIpKSwgbmFtZXNfdG89InZhcmlhYmxlIiwgdmFsdWVzX3RvPSJ2YWx1ZSIpDQojIGRlbnNpZGFkZXMgcG9yIHZhcmlhYmxlDQpwbHRfZGVuc2l0eSA9IA0KICBnZ3Bsb3QoZ2RhdCwgYWVzKHg9dmFsdWUsIHk9dmFyaWFibGUsIGNvbG9yPWNsdXN0ZXIsIHBvaW50X2NvbG9yPWNsdXN0ZXINCiAgICAgICAgICAgICAgICAgLCBmaWxsPWNsdXN0ZXIpKSArDQogIGdncmlkZ2VzOjpnZW9tX2RlbnNpdHlfcmlkZ2VzKA0KICAgIGFscGhhPTAuNSwgc2NhbGU9MQ0KICAgICxqaXR0ZXJlZF9wb2ludHM9VCwgcG9zaXRpb249cG9zaXRpb25fcG9pbnRzX2ppdHRlcihoZWlnaHQ9MCkNCiAgICAscG9pbnRfc2hhcGU9InwiLCBwb2ludF9zaXplPTINCiAgKSArDQogIHRoZW1lX21pbmltYWwoKSArDQogIE5VTEwNCg0KcHJpbnQocGx0X2RlbnNpdHkpDQoNCmBgYA0KDQpgYGB7cn0NCiMgYm94cGxvdHMgcG9yIGNsdXN0ZXINCnBsdF9ib3hwbG90ID0NCiAgZ2dwbG90KGdkYXQsIGFlcyh4PXZhcmlhYmxlLCB5PXZhbHVlLCBjb2xvcj1jbHVzdGVyKSkgKw0KICBmYWNldF93cmFwKH5jbHVzdGVyLCBuY29sPTIsIHNjYWxlcz0iZnJlZV95IikgKw0KICBnZW9tX2JveHBsb3QoKSArDQogIHRoZW1lX21pbmltYWwoKSArDQogIHRoZW1lKGF4aXMudGV4dC54PWVsZW1lbnRfdGV4dChhbmdsZT0tOTApKSArDQogIE5VTEwNCg0KcHJpbnQocGx0X2JveHBsb3QpDQoNCmBgYA0KDQpQb3Igw7psdGltbywgcmVwcmVzZW50YW1vcyBsb3MgY2x1c3RlcnMgZW4gdW4gbWFwYToNCg0KYGBge3IgbWFwYX0NCiMgZGF0b3MgY29uIGluZm8gZ2VvZ3JhZmljYQ0KZ2RhdCA9IGRhdF9zZiAlPiUgDQogIGxlZnRfam9pbihkYXRfaGMsIGJ5PSJpc28zYyIpICU+JSANCiAgZmlsdGVyKGlzbzNjICE9ICJBVEEiKSAlPiUgIyBzaW4gYW50YXJ0aWNhDQogIG11dGF0ZSgNCiAgICBjbHVzdGVyID0gaWZlbHNlKG91dGxpZXIgPT0gMSwgIm91dGxpZXIiLCBjbHVzdGVyKQ0KICApDQojIG1hcGENCnBsdCA9IA0KICBnZ3Bsb3QoZ2RhdCwgYWVzKGZpbGw9Y2x1c3RlciwgbGFiZWw9Y291bnRyeSkpICsNCiAgZ2VvbV9zZigpICsNCiAgdGhlbWVfbWluaW1hbCgpICsNCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uPSJib3R0b20iKSArDQogIE5VTEwNCg0KZ2dwbG90bHkoIHBsdCwgd2lkdGg9ODAwICkNCmBgYA0KDQoNCiMgRXh0cmFzDQoNCiMjIFRlc3QgZGUgSG9wa2lucw0KDQpFdmFsdWFtb3Mgc2kgZXhpc3RlIHRlbmRlbmNpYSBhbCBhZ3J1cGFtaWVudG8gdXNhbmRvIGVsICoqdGVzdCBkZSBIb3BraW5zKiouDQoNCmBgYHtyIGhvcGtpbnN9DQpob3BraW5zID0gZmFjdG9leHRyYTo6Z2V0X2NsdXN0X3RlbmRlbmN5KGRhdF9jLCBuPTEwMCwgc2VlZD0zMjEpDQoNCmNhdCgiSG9wa2lucyA9IiwgaG9wa2lucyRob3BraW5zX3N0YXQpDQoNCmBgYA0KDQpTZWfDum4gbGEgZG9jdW1lbnRhY2nDs24gZGUgbGEgZnVuY2nDs24gYGdldF9jbHVzdF90ZW5kZW5jeSgpYCwgdW4gSG9wa2lucyBtw6FzIGFsdG8gaW5kaWNhIG1heW9yIHRlbmRlbmNpYSBhbCBjbHVzdGVyaW5nLiBFbiBlc3RlIGNhc28sIGVsIHZhbG9yIGRlbCBlc3RhZMOtc3RpY28gZXMgZXZpZGVudGVtZW50ZSBzdXBlcmlvciBhIDAuNSwgZW50b25jZXMgcG9kZW1vcyBjb25jbHVpciBxdWUgbG9zIHBhw61zZXMgbm8gZXN0w6FuIGRpc3RyaWJ1aWRvcyB1bmlmb3JtZW1lbnRlIGVuIGVsIGVzcGFjaW8gZGUgbGFzIHZhcmlhYmxlcy4gRXMgZGVjaXIsIHByZXNlbnRhbiB1bmEgKip0ZW5kZW5jaWEgYSBhZ3J1cGFyc2UqKi4NCg0KDQojIyBHYXAgc3RhdGlzdGljDQoNClVuYSBmb3JtYSBkZSBmb3JtYWxpemFyIGVsIGNyaXRlcmlvIGRlICJwdW50byBkZSBxdWllYnJlIiBlcyBlbCAqKkdhcCBzdGF0aXN0aWMqKi4gw4lzdGUgY2FsY3VsYSBsYSBkaWZlcmVuY2lhIGxvZ2Fyw610bWljYSBlbnRyZSBsYSB2YXJpYWJpbGlkYWQgaW50cmEtY2x1c3RlciBkZWwgZGF0YXNldCByZWFsIHkgZGF0YXNldHMgc2ltdWxhZG9zIGNvbiBkaXN0cmlidWNpw7NuIHVuaWZvcm1lLg0KDQpgYGB7ciB9DQpzZXQuc2VlZCgzMjEpDQpmdml6X25iY2x1c3QoZGF0X2MsIEZVTmNsdXN0ZXI9aGN1dCwgbWV0aG9kPSJnYXBfc3RhdCIsIGsubWF4PTIwDQogICAgICAgICAgICAgLG5zdGFydD01MCwgbmJvb3Q9MTAwDQogICAgICAgICAgICAgLGRpc3M9ZGlzdChkYXRfYywgbWV0aG9kPSJtYW5oYXR0YW4iKSwgaGNfbWV0aG9kPSJhdmVyYWdlIikNCg0KYGBgDQoNCkVsIGNyaXRlcmlvIGluZGljYSBxdWUgc2UgZGViZSBlbGVnaXIgZWwgbcOtbmltbyBLIGEgcGFydGlyIGRlbCBjdWFsIGxhICJ0YXNhIGRlIGNyZWNpZW1pZW50byIgZGVsIGVzdGFkw61zdGljbyBzZSByZWR1Y2UuIFNpbiBlbWJhcmdvLCBlbiBwcmVzZW5jaWEgZGUgb3V0bGllcnMgeSBzdWJjbHVzdGVycyBjb24gZGlzdGludG9zIGdyYWRvcyBkZSBzZXBhcmFjacOzbiwgZWwgY29tcG9ydGFtaWVudG8gZXMgbm8gbW9uw7N0b25vLCBwb3IgbG8gY3VhbCBlcyBuZWNlc2FyaW8gbWlyYXIgdG9kYSBsYSBjdXJ2YS4gUGFyYSBtw6FzIGRldGFsbGVzIHZlciBbZWwgcGFwZXIgb3JpZ2luYWxdKGh0dHBzOi8vc3RhdHdlYi5zdGFuZm9yZC5lZHUvfmd3YWx0aGVyL2dhcCkuDQoNCg0K